//
// Created by Administrator on 2023/11/17.
//
#include "iostream"
#include "cstring"

using namespace std;

const int N = 510;
int n, m;
int g[N][N], dist[N];
bool st[N];

//每次从dist数组中选择最小的，进行更新
void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    //每次循环可以确定一个点
    for (int i = 0; i < n ; ++i) {

        int t = -1;
        //遍历dist数组，找到没有确定最短路径中距离原点最近的
        for (int j = 1; j <= n; ++j) {
            //st 表示确定最短路径 dist为距离
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        st[t] = true;

        //遍历所有经过t可以到达的结点

        for (int j = 1; j <= n; ++j) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    if (dist[n] == 0x3f3f3f3f) cout << -1;
    else cout << dist[n];
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = z;
    }
    dijkstra();
}